home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / src / haeberli / libgutil / hideline.c < prev    next >
C/C++ Source or Header  |  1994-08-01  |  30KB  |  1,578 lines
  1. /*
  2.  * Copyright 1991, 1992, 1993, 1994, Silicon Graphics, Inc.
  3.  * All Rights Reserved.
  4.  *
  5.  * This is UNPUBLISHED PROPRIETARY SOURCE CODE of Silicon Graphics, Inc.;
  6.  * the contents of this file may not be disclosed to third parties, copied or
  7.  * duplicated in any form, in whole or in part, without the prior written
  8.  * permission of Silicon Graphics, Inc.
  9.  *
  10.  * RESTRICTED RIGHTS LEGEND:
  11.  * Use, duplication or disclosure by the Government is subject to restrictions
  12.  * as set forth in subdivision (c)(1)(ii) of the Rights in Technical Data
  13.  * and Computer Software clause at DFARS 252.227-7013, and/or in similar or
  14.  * successor clauses in the FAR, DOD or NASA FAR Supplement. Unpublished -
  15.  * rights reserved under the Copyright Laws of the United States.
  16.  */
  17. /*
  18.  *    hideline -
  19.  *        A hidden line algotithm.
  20.  *
  21.  *            Paul Haeberli - 1990
  22.  *
  23.  *    exports
  24.  *
  25.     void hiddendirdrop(dir,thresh)
  26.     void hiddencolorthresh(delta)    in range 0.0..1.0
  27.     void hiddensilwidth(min,max)
  28.     void hiddenhalowidth(wid)
  29.     void hiddenfacewidths(min,max,inter)
  30.     void hiddenextend(sil,face,var)
  31.  
  32.     void hiddenline(tlname,dfunc,wfunc)
  33.  
  34.         void beginhideline(dfunc,wfunc);
  35.     void hiddentri(atile)
  36.         void endhideline();
  37.  *
  38.  */
  39. #include "stdio.h"
  40. #include "math.h"
  41. #include "trilist.h"
  42. #include "simple.h"
  43. #include "vect.h"
  44. #include "hideline.h"
  45.  
  46. float frand();
  47. void beginhideline();
  48. void endhideline();
  49. void hiddentri();
  50.  
  51. #define ISTRANS(c)    (((c)>>24) == 0x00)
  52.  
  53. typedef struct edge {    /* first 4 lines must be identical to tile struct */
  54.     struct edge *next;
  55.     FLOAT xmin, xmax;
  56.     FLOAT ymin, ymax;
  57.     FLOAT zmin, zmax;
  58.     VECT edgeeq;
  59.     VECT pos[2];
  60.     long col[2];
  61.     int backfacing;
  62.     int type;
  63.     FLOAT delc;
  64. } edge;
  65.  
  66. static edge *edgemalloc();
  67. static void freeedge();
  68. static edge *cloneedge();
  69. static void freeedgelist();
  70. static tile *tilemalloc();
  71. static void freetile();
  72. static void freetilelist();
  73. static FLOAT edgedist2d();
  74. static FLOAT planedist3d();
  75. static FLOAT cdist();
  76. static FLOAT colordel();
  77. static int geomsame();
  78. static int geommatch0();
  79. static int geommatch1();
  80. static int colorsame();
  81. static int colormatch0();
  82. static int colormatch1();
  83. static int vertsame();
  84. static int hasarea();
  85. static void edgedomain();
  86. static FLOAT silwidth();
  87. static void extendedge();
  88. static tile *freepast();
  89. static void findedges();
  90. static int bbox2d();
  91. static int bbox3d();
  92. static int vsame();
  93. static int edgeontri();
  94. static int edgeintertri();
  95. static int posinside();
  96. static int tritriinter();
  97. static int couldhide();
  98. static int edgeinbackoftriplane();
  99. static int trisplitedge();
  100. static void planesplitedge();
  101. static void hidehaloedge();
  102. static int haloedge();
  103. static void dohidehaloedge();
  104. static void dohideedge();
  105. static void dohidepoint();
  106. static int compar();
  107. static tile *ysortlist();
  108. static void putline();
  109. static void readtilelist(char *name);
  110.  
  111. #define NOBACKFACE
  112. #define NINCHUNK    300
  113.  
  114. #define WIDTH_MIN    (0.0001)
  115.  
  116. #define EDGEEXTEND_SIL    (0.1)
  117. #define EDGEEXTEND_INT    (0.0)
  118. #define EDGEEXTEND_MIN    (0.0)    /* these are scaled by EDGEEXTEND_SIL */
  119. #define EDGEEXTEND_MAX     (1.0)
  120.  
  121. #define ALMOSTPLANAR    (0.999)
  122.  
  123. #define EDGETYPE_UNKNOWN    0
  124. #define EDGETYPE_SIL        1
  125. #define EDGETYPE_INT        2
  126. #define EDGETYPE_LINE        3
  127. #define EDGETYPE_POINT        4
  128. #define EDGETYPE_TEXT        5
  129.  
  130. #define INTER_NONE    0
  131. #define INTER_TOUCHES    1
  132. #define INTER_COVERS    2
  133.  
  134. static int (*linefunc)();
  135. static int (*widthfunc)();
  136. static edge *halohead;
  137. static FLOAT curwidth;
  138.  
  139. static FLOAT cthresh = 0.1;
  140.  
  141. static FLOAT silwidthmin = 0.002;
  142. static FLOAT silwidthmax = 0.006;
  143.  
  144. static FLOAT halowidth = 0.008;
  145.  
  146. static FLOAT faceminwidth = 0.0005;
  147. static FLOAT facemaxwidth = 0.0015;
  148. static FLOAT intersectwidth = 0.0005;
  149.  
  150. static FLOAT extendsil = 0.05;
  151. static FLOAT extendface = 0.05;
  152. static FLOAT extendvar = 0.5;
  153.  
  154. static FLOAT putwidth = -1.0;
  155. static edge *fedges;
  156. static tile *ftiles;
  157.  
  158. static VECT  dropdir;
  159. static FLOAT dropthresh = 0.0;
  160.  
  161. static void putpoint(float *p, float width);
  162.  
  163. /*
  164.  *    config functions
  165.  *
  166.  *
  167.  */
  168. void hiddendirdrop(dir,thresh)
  169. vect *dir;
  170. float thresh;
  171. {
  172.     dropdir.x = dir->x;
  173.     dropdir.y = dir->y;
  174.     dropdir.z = dir->z;
  175.     VNORMAL(&dropdir);
  176.     dropthresh = thresh;
  177. }
  178.  
  179. void hiddencolorthresh(delta)    /* 0.0..1.0 */
  180. float delta;
  181. {
  182.     cthresh = delta;
  183. }
  184.  
  185. void hiddensilwidth(min,max)
  186. float min, max;
  187. {
  188.     silwidthmin = min;
  189.     silwidthmax = max;
  190. }
  191.  
  192. void hiddenhalowidth(wid)
  193. float wid;
  194. {
  195.     halowidth = wid;
  196. }
  197.  
  198. void hiddenfacewidths(min,max,inter)
  199. float min, max, inter;
  200. {
  201.     faceminwidth = min;
  202.     facemaxwidth = min;
  203.     intersectwidth = inter;
  204. }
  205.  
  206. void hiddenextend(sil,face,var)
  207. float sil,face,var;
  208. {
  209.     extendsil = sil;
  210.     extendface = face;
  211.     extendvar = var;
  212. }
  213.  
  214. /*
  215.  *    fast alloc for edges and tiles
  216.  *
  217.  *
  218.  */
  219. static edge *edgemalloc()
  220. {
  221.     edge *e;
  222.     int i;
  223.  
  224.     if(!fedges) {
  225.            e = (edge *)mymalloc(NINCHUNK*sizeof(edge));
  226.         for(i=0; i<NINCHUNK; i++)
  227.         freeedge(e++);
  228.     }
  229.     e = fedges;
  230.     fedges = fedges->next;
  231.     return e;
  232. }
  233.  
  234. static void freeedge(e)
  235. edge *e;
  236. {
  237.    if( e ) {
  238.        e->next = fedges;
  239.        fedges = e;
  240.    }
  241. }
  242.  
  243. static edge *cloneedge(e) 
  244. edge *e;
  245. {
  246.     edge *c; 
  247.  
  248.     c = edgemalloc();
  249.     *c = *e;
  250.     c->next = 0;
  251.     return c;
  252. }
  253.  
  254. static void freeedgelist(e)
  255. edge *e;
  256. {
  257.     edge *ne;
  258.  
  259.     if(e) {
  260.     while(e) {
  261.         ne = e->next;
  262.         freeedge(e);
  263.         e = ne;
  264.     }
  265.     }
  266. }
  267.  
  268. static tile *tilemalloc()
  269. {
  270.     tile *t;
  271.     int i;
  272.  
  273.     if(!ftiles) {
  274.            t = (tile *)mymalloc(NINCHUNK*sizeof(tile));
  275.         for(i=0; i<NINCHUNK; i++)
  276.         freetile(t++);
  277.     }
  278.     t = ftiles;
  279.     ftiles = ftiles->next;
  280.     return t;
  281. }
  282.  
  283. static void freetile(t)
  284. tile *t;
  285. {
  286.     if( t ) {
  287.            t->next = ftiles;
  288.            ftiles = t;
  289.     }
  290. }
  291.  
  292. static void freetilelist(t)
  293. tile *t;
  294. {
  295.     tile *nt;
  296.  
  297.     if(t) {
  298.     while(t) {
  299.         nt = t->next;
  300.         freetile(t);
  301.         t = nt;
  302.     }
  303.     }
  304. }
  305.  
  306. /*
  307.  *    hidden line stuff follows
  308.  *
  309.  *
  310.  */
  311. void hiddenline(tlname,dfunc,wfunc)
  312. char *tlname;
  313. int (*dfunc)();
  314. int (*wfunc)();
  315. {
  316.     beginhideline(dfunc,wfunc);
  317.     readtilelist(tlname);
  318.     endhideline();
  319. }
  320.  
  321. static tile *tiles;
  322. static edge *edgelist;
  323.  
  324. void beginhideline(dfunc,wfunc)
  325. int (*dfunc)();
  326. int (*wfunc)();
  327. {
  328.     linefunc = dfunc;
  329.     widthfunc = wfunc;
  330.     tiles = 0;
  331.     edgelist = 0;
  332. }
  333.  
  334. void endhideline()
  335. {
  336.     tiles = ysortlist(tiles);
  337.     findedges(tiles,edgelist);
  338. }
  339.  
  340. static FLOAT edgedist2d(edgeeq,pos)
  341. VECT *edgeeq, *pos;
  342. {
  343.     return (edgeeq->x*pos->x) + (edgeeq->y*pos->y) + edgeeq->w;
  344. }
  345.  
  346. static FLOAT planedist3d(planeeq,pos)
  347. VECT *planeeq, *pos;
  348. {
  349.     return (planeeq->x*pos->x) + 
  350.               (planeeq->y*pos->y) + 
  351.              (planeeq->z*pos->z) + planeeq->w;
  352. }
  353.  
  354. static edge *lineedge(tile *t, int v1, int v2, int type)
  355. {
  356.     edge *e;
  357.  
  358.     e = edgemalloc();
  359.     e->pos[0] = t->pos[v1];
  360.     e->col[0] = t->col[v1];
  361.     e->pos[1] = t->pos[v2];
  362.     e->col[1] = t->col[v2];
  363.     e->backfacing = 0;
  364.     e->type = type;
  365.     edgedomain(e);
  366.     return e;
  367. }
  368.  
  369. static void readtilelist(char *name)
  370. {
  371.     tile atile;
  372.     int i, ntri;
  373.     trilisttri tri;
  374.  
  375.     ntri = tlopen(name);
  376.     for(i=0; i<ntri; i++) {
  377.     tlread(&tri);
  378.     atile.pos[0].x = ASPECT*tri.x0;
  379.     atile.pos[0].y = tri.y0;
  380.     atile.pos[0].z = tri.z0;
  381.     atile.pos[1].x = ASPECT*tri.x1;
  382.     atile.pos[1].y = tri.y1;
  383.     atile.pos[1].z = tri.z1;
  384.     atile.pos[2].x = ASPECT*tri.x2;
  385.     atile.pos[2].y = tri.y2;
  386.     atile.pos[2].z = tri.z2;
  387.     atile.col[0] = tri.c0;
  388.     atile.col[1] = tri.c1;
  389.     atile.col[2] = tri.c2;
  390.     hiddentri(&atile);
  391.     }
  392.     tlclose();
  393. }
  394.  
  395. void hiddentri(atile)
  396. tile *atile;
  397. {
  398.     VECT norm, temp;
  399.     FLOAT dx, dy, w, mag;
  400.     int j, s0, s1, s2;
  401.     tile *ttile;
  402.     edge *e;
  403.  
  404.     ttile = tilemalloc();
  405.     *ttile = *atile;
  406.     atile = ttile;
  407.  
  408.     atile->transparent = 0;
  409.     atile->transparent |= ISTRANS(atile->col[0]);
  410.     atile->transparent |= ISTRANS(atile->col[1]);
  411.     atile->transparent |= ISTRANS(atile->col[2]);
  412.     atile->col[0] &= 0xffffff;
  413.     atile->col[1] &= 0xffffff;
  414.     atile->col[2] &= 0xffffff;
  415.     if(TRINORMAL(atile->pos+0,atile->pos+1,atile->pos+2,&norm,TOLERANCE/100.0)) {
  416.     if(norm.z<0.0) {
  417. #ifdef NOBACKFACE
  418.         freetile(atile);
  419.         return;
  420. #else
  421.         norm.x = -norm.x;
  422.         norm.y = -norm.y;
  423.         norm.z = -norm.z;
  424.         temp = atile->pos[1];
  425.         atile->pos[1] = atile->pos[2];;
  426.         atile->pos[2] = temp;
  427.         atile->backfacing = 1;
  428. #endif
  429.     } else {
  430.         atile->backfacing = 0;
  431.     }
  432.     VPLANE(&norm,atile->pos+0,&atile->plane);
  433.     for(j=0; j<3; j++) {
  434.         dx = atile->pos[(j+1)%3].y-atile->pos[j].y;
  435.         dy = atile->pos[(j+1)%3].x-atile->pos[j].x;
  436.         mag = sqrt(dx*dx+dy*dy);
  437.         dx = dx/mag;
  438.         dy = -dy/mag;
  439.         w = dx*atile->pos[j].x+dy*atile->pos[j].y;
  440.         atile->edgeeq[j].x = dx;
  441.         atile->edgeeq[j].y = dy;
  442.         atile->edgeeq[j].w = -w;
  443.     }
  444.  
  445.     atile->xmin = atile->xmax = atile->pos[0].x;
  446.     atile->ymin = atile->ymax = atile->pos[0].y;
  447.     atile->zmin = atile->zmax = atile->pos[0].z;
  448.     for(j=1; j<3; j++) {
  449.         if(atile->xmin>atile->pos[j].x)
  450.         atile->xmin=atile->pos[j].x;
  451.         if(atile->xmax<atile->pos[j].x)
  452.         atile->xmax=atile->pos[j].x;
  453.         if(atile->ymin>atile->pos[j].y)
  454.         atile->ymin=atile->pos[j].y;
  455.         if(atile->ymax<atile->pos[j].y)
  456.         atile->ymax=atile->pos[j].y;
  457.         if(atile->zmin>atile->pos[j].z)
  458.         atile->zmin=atile->pos[j].z;
  459.         if(atile->zmax<atile->pos[j].z)
  460.         atile->zmax=atile->pos[j].z;
  461.     }
  462.     atile->next = tiles;
  463.     tiles = atile;
  464.     } else {
  465.     s0 = vertsame(atile->pos+0,atile->pos+1);
  466.     s1 = vertsame(atile->pos+1,atile->pos+2);
  467.     s2 = vertsame(atile->pos+2,atile->pos+0);
  468.     if(s0 && s1 && s2) {
  469.         e = lineedge(atile,0,0,EDGETYPE_POINT);
  470.         e->next = edgelist;
  471.         edgelist = e;
  472.     } else if(s0 || s1 || s2) {
  473.         if(s0)
  474.         e = lineedge(atile,1,2,EDGETYPE_LINE);
  475.         else
  476.         e = lineedge(atile,0,1,EDGETYPE_LINE);
  477.         e->next = edgelist;
  478.         edgelist = e;
  479.     } else {
  480.         fprintf(stderr,"very small tri found!!\n");
  481.     }
  482.     freetile(atile);
  483.     }
  484. }
  485.  
  486. static FLOAT cdist(c0,c1)
  487. long c0, c1;
  488. {
  489.     int d, td;
  490.  
  491.     d = ((c0>>0)&0xff) - ((c1>>0)&0xff);
  492.     if(d<0)
  493.     d = -d;
  494.     td = d;
  495.     d = ((c0>>8)&0xff) - ((c1>>8)&0xff);
  496.     if(d<0)
  497.     d = -d;
  498.     td += d;
  499.     d = ((c0>>16)&0xff) - ((c1>>16)&0xff);
  500.     if(d<0)
  501.     d = -d;
  502.     td += d;
  503.     return td/(3*255.0);
  504. }
  505.  
  506. static FLOAT colordel(e0,e1,ord)
  507. edge *e0, *e1;
  508. int ord;
  509. {
  510.     switch(ord) {
  511.     case 1:
  512.         return (cdist(e0->col[0],e1->col[0]) + cdist(e0->col[1],e1->col[1]))/2.0;
  513.         break;
  514.     case 2:
  515.         return (cdist(e0->col[0],e1->col[1]) + cdist(e0->col[1],e1->col[0]))/2.0;
  516.         break;
  517.     default:
  518.         fprintf(stderr,"colordel: bad poop\n");
  519.         exit(1);
  520.         break;
  521.     }
  522.  
  523. }
  524.  
  525. static int geomsame(e0,e1)
  526. edge *e0, *e1;
  527. {
  528.     if(geommatch1(e0,e1))
  529.     return 2;
  530.     return 0;
  531. }
  532.  
  533. #define POSDIFF(a,b)    ((a)!=(b))
  534.  
  535. static int geommatch0(e0,e1)
  536. edge *e0, *e1;
  537. {
  538.     VECT *v0, *v1;
  539.  
  540.     v0 = e0->pos+0;
  541.     v1 = e1->pos+0;
  542.     if(POSDIFF(v0->x,v1->x))
  543.     return 0;
  544.     if(POSDIFF(v0->y,v1->y))
  545.     return 0;
  546.     if(POSDIFF(v0->y,v1->y))
  547.     return 0;
  548.  
  549.     v0 = e0->pos+1;
  550.     v1 = e1->pos+1;
  551.     if(POSDIFF(v0->x,v1->x))
  552.     return 0;
  553.     if(POSDIFF(v0->y,v1->y))
  554.     return 0;
  555.     if(POSDIFF(v0->y,v1->y))
  556.     return 0;
  557.  
  558.     return 1;
  559. }
  560.  
  561. static int geommatch1(e0,e1)
  562. edge *e0, *e1;
  563. {
  564.     VECT *v0, *v1;
  565.  
  566.     v0 = e0->pos+0;
  567.     v1 = e1->pos+1;
  568.     if(POSDIFF(v0->x,v1->x))
  569.     return 0;
  570.     if(POSDIFF(v0->y,v1->y))
  571.     return 0;
  572.     if(POSDIFF(v0->y,v1->y))
  573.     return 0;
  574.  
  575.     v0 = e0->pos+1;
  576.     v1 = e1->pos+0;
  577.     if(POSDIFF(v0->x,v1->x))
  578.     return 0;
  579.     if(POSDIFF(v0->y,v1->y))
  580.     return 0;
  581.     if(POSDIFF(v0->y,v1->y))
  582.     return 0;
  583.  
  584.     return 1;
  585. }
  586.  
  587. static int colorsame(e0,e1)
  588. edge *e0, *e1;
  589. {
  590.     if(colormatch0(e0,e1))
  591.     return 1;
  592.     if(colormatch1(e0,e1))
  593.     return 2;
  594.     return 0;
  595. }
  596.  
  597. static int colormatch0(e0,e1)
  598. edge *e0, *e1;
  599. {
  600.     if(cdist(e0->col[0],e1->col[0])>=cthresh)
  601.     return 0;
  602.     if(cdist(e0->col[1],e1->col[1])>=cthresh)
  603.     return 0;
  604.     return 1;
  605. }
  606.  
  607. static int colormatch1(e0,e1)
  608. edge *e0, *e1;
  609. {
  610.     if(cdist(e0->col[0],e1->col[1])>=cthresh)
  611.     return 0;
  612.     if(cdist(e0->col[1],e1->col[0])>=cthresh)
  613.     return 0;
  614.     return 1;
  615. }
  616.  
  617. static int vertsame(v0,v1)
  618. FLOAT *v0, *v1;
  619. {
  620.     if(v0[0] != v1[0])
  621.     return 0;
  622.     if(v0[1] != v1[1])
  623.     return 0;
  624.     if(v0[2] != v1[2])
  625.     return 0;
  626.     return 1;
  627. }
  628.  
  629. static int hasarea(tri)
  630. trilisttri *tri;
  631. {
  632.     if(vertsame(&tri->x0,&tri->x1))
  633.     return 0;
  634.     if(vertsame(&tri->x1,&tri->x2))
  635.     return 0;
  636.     if(vertsame(&tri->x2,&tri->x0))
  637.     return 0;
  638.     return 1;
  639. }
  640.  
  641. static void edgedomain(e)
  642. edge *e;
  643. {
  644.     FLOAT dx, dy, mag, w;
  645.  
  646.     e->xmin = e->xmax = e->pos[0].x;
  647.     e->ymin = e->ymax = e->pos[0].y;
  648.     e->zmin = e->zmax = e->pos[0].z;
  649.     if(e->xmin>e->pos[1].x)
  650.     e->xmin=e->pos[1].x;
  651.     if(e->xmax<e->pos[1].x)
  652.     e->xmax=e->pos[1].x;
  653.     if(e->ymin>e->pos[1].y)
  654.     e->ymin=e->pos[1].y;
  655.     if(e->ymax<e->pos[1].y)
  656.     e->ymax=e->pos[1].y;
  657.     if(e->zmin>e->pos[1].z)
  658.     e->zmin=e->pos[1].z;
  659.     if(e->zmax<e->pos[1].z)
  660.     e->zmax=e->pos[1].z;
  661.     dx = e->pos[1].y-e->pos[0].y;
  662.     dy = e->pos[1].x-e->pos[0].x;
  663.     mag = sqrt(dx*dx+dy*dy);
  664.     dx = dx/mag;
  665.     dy = -dy/mag;
  666.     w = dx*e->pos[0].x+dy*e->pos[0].y;
  667.     e->edgeeq.x = dx;
  668.     e->edgeeq.y = dy;
  669.     e->edgeeq.w = -w;
  670. }
  671.  
  672. static FLOAT silwidth(e)
  673. edge *e;
  674. {
  675.     FLOAT dx, dy, mag, val;
  676.   
  677.     dx = e->pos[1].x - e->pos[0].x;
  678.     dy = e->pos[1].y - e->pos[0].y;
  679.     mag = sqrt(dx*dx+dy*dy);
  680.     val = (1.0+(dx/mag))/2.0;
  681.     return FLERP(silwidthmin,silwidthmax,val);
  682. }
  683.  
  684. static void extendedge(e,ee,exmag)
  685. edge *e, *ee;
  686. float exmag;
  687. {
  688.     FLOAT dx, dy, dz, mag, extend;
  689.  
  690.     dx = e->pos[1].x-e->pos[0].x;
  691.     dy = e->pos[1].y-e->pos[0].y;
  692.     dz = e->pos[1].z-e->pos[0].z;
  693.     mag = sqrt(dx*dx+dy*dy);
  694.     if(mag>TOLERANCE) {
  695.     extend = exmag*FLERP(1.0-extendvar,1.0+extendvar,frand());
  696.     if(extend<0.0)
  697.         extend = 0.0;
  698.     dx = (extend*dx)/mag;
  699.     dy = (extend*dy)/mag;
  700.     dz = (extend*dz)/mag;
  701.     ee->pos[0].x = e->pos[0].x-dx;
  702.     ee->pos[0].y = e->pos[0].y-dy;
  703.     ee->pos[0].z = e->pos[0].z-dz+0.0001;
  704.     ee->pos[1].x = e->pos[1].x+dx;
  705.     ee->pos[1].y = e->pos[1].y+dy;
  706.     ee->pos[1].z = e->pos[1].z+dz+0.0001;
  707.     edgedomain(ee);
  708.     ee->backfacing = e->backfacing;
  709.     } else 
  710.     *ee = *e;
  711. }
  712.  
  713. static tile *freepast(tlist,y) 
  714. tile *tlist;
  715. FLOAT y;
  716. {
  717.     tile *tl, *ntl;
  718.  
  719.     while(tlist && tlist->ymax<y) {
  720.     ntl = tlist->next;
  721.     freetile(tlist);
  722.     tlist = ntl;
  723.     }
  724.     if(tlist) {
  725.     tl = tlist;
  726.     while(tl->next) {
  727.         if(tl->next->ymin>y)
  728.         return tlist;
  729.         if(tl->next->ymax<y) {
  730.         ntl = tl->next->next;
  731.         freetile(tl->next);
  732.         tl->next = ntl;
  733.         } else 
  734.         tl = tl->next;
  735.     }
  736.     }
  737.     return tlist;
  738. }
  739.  
  740. static int dodropedge(edge *e)
  741. {
  742.     VECT dir;
  743.     FLOAT dx, dy, dz, dot;
  744.    
  745.     if(dropthresh < 0.0001)
  746.     return 0;
  747.     VSUB(e->pos+0,e->pos+1,&dir);
  748.     VNORMAL(&dir);
  749.     dot = VDOT(&dir,&dropdir);
  750.     if(dot<0.0)
  751.     dot = -dot;
  752.     if(dot<dropthresh)
  753.     return 0;
  754.     else
  755.     return 1;
  756. }
  757.  
  758. static void findedges(tile *tlist, edge *edgelist)
  759. {
  760.     int i, gs;
  761.     edge *e, *cur, *curp, *head;
  762.     edge eedge;
  763.     tile *tl, *otl;
  764.     FLOAT top, maxextend;
  765.     edge interedge;
  766.     edge *halotail;
  767.  
  768.     maxextend = (1.0+extendvar)*MAX(EDGEEXTEND_SIL,EDGEEXTEND_INT);
  769.  
  770. /* get edges from all the triangles */
  771.     tl = tlist;
  772.     while(tl) {        
  773.     e = edgemalloc();
  774.     e->pos[0] = tl->pos[0];
  775.     e->col[0] = tl->col[0];
  776.     e->pos[1] = tl->pos[1];
  777.     e->col[1] = tl->col[1];
  778.     e->backfacing = tl->backfacing;
  779.     e->type = EDGETYPE_UNKNOWN;
  780.     edgedomain(e);
  781.     e->next = edgelist;
  782.     edgelist = e;
  783.  
  784.     e = edgemalloc();
  785.     e->pos[0] = tl->pos[1];
  786.     e->col[0] = tl->col[1];
  787.     e->pos[1] = tl->pos[2];
  788.     e->col[1] = tl->col[2];
  789.     e->backfacing = tl->backfacing;
  790.     e->type = EDGETYPE_UNKNOWN;
  791.     edgedomain(e);
  792.     e->next = edgelist;
  793.     edgelist = e;
  794.  
  795.     e = edgemalloc();
  796.     e->pos[0] = tl->pos[2];
  797.     e->col[0] = tl->col[2];
  798.     e->pos[1] = tl->pos[0];
  799.     e->col[1] = tl->col[0];
  800.     e->backfacing = tl->backfacing;
  801.     e->type = EDGETYPE_UNKNOWN;
  802.     edgedomain(e);
  803.     e->next = edgelist;
  804.     edgelist = e;
  805.  
  806.     tl = tl->next;
  807.     }
  808.  
  809. /* sort the edges in y */
  810.     edgelist = (edge *)ysortlist(edgelist);
  811.  
  812. /* Classify all edges */
  813.     head = edgelist;
  814.     halohead = 0;
  815.     halotail = 0;
  816.     while(head) {
  817.     curp = head;
  818.     cur = head->next;
  819.     top = head->ymax;
  820.  
  821.     if(head && head->type == EDGETYPE_UNKNOWN) {
  822. /* find another edge with the same geometry */
  823.         while(cur) {
  824.         if(cur->ymin>top) {
  825.             cur = 0;
  826.             break;
  827.         }
  828.         if(gs=geomsame(cur,head) && cur->type == EDGETYPE_UNKNOWN) 
  829.             break;
  830.         curp = cur;
  831.         cur = cur->next;
  832.         }
  833.  
  834. /* if geometry is unique, the edge is a silouette edge */
  835.         if(!cur) {
  836.         head->type = EDGETYPE_SIL;
  837.  
  838. /* clone it and add it to the halo list */
  839.             cur = cloneedge(head);
  840.             if(!halohead) {
  841.             halohead = cur;
  842.             halotail = cur;
  843.             } else {
  844.             halotail->next = cur;
  845.             halotail = cur;
  846.             }
  847.     
  848. /* if geometry is duplicated it's an internal edge */
  849.         } else {
  850.             if(!colorsame(cur,head)) {
  851.             head->delc = colordel(cur,head,gs);
  852.             head->type = EDGETYPE_INT;
  853.             }
  854.             e = curp->next;
  855.             curp->next = cur->next;
  856.             freeedge(e);
  857.         }
  858.     } 
  859.     head = head->next;
  860.     } 
  861.  
  862. /* find all the places where two triangles intersect */
  863.     tl = tlist;
  864.     curwidth = intersectwidth;
  865.     while(tl) {
  866.     otl = tl->next;
  867.     while(otl) {
  868.         if(otl->ymin>tl->ymax)
  869.         break;
  870.         if(tritriinter(tl,otl,&interedge)) 
  871.         hidehaloedge(tlist,halohead,&interedge); 
  872.         otl = otl->next;
  873.     }
  874.     tl = tl->next;
  875.     }
  876.  
  877. /* go thru the edges in order */
  878.     head = edgelist;
  879.     while(head) {
  880.  
  881. /* free triangles past */
  882.     tlist = freepast(tlist,head->ymin-maxextend);
  883.  
  884.     if(dodropedge(head)) {
  885. /* if drop edge */
  886.  
  887.     } else if(head->type == EDGETYPE_SIL || head->type == EDGETYPE_LINE) {
  888. /* if silouette edge */
  889. #ifdef DASHEDLINES
  890.         curwidth = WIDTH_MIN;
  891.         extendedge(head,&eedge,extendsil);
  892.         hidehaloedge(tlist,halohead,&eedge); 
  893.         curwidth = silwidth(head);
  894.         dashedge(head);
  895.         hidehaloedge(tlist,halohead,head); 
  896. #endif
  897.         curwidth = silwidth(head);
  898.         extendedge(head,&eedge,extendsil);
  899.         hidehaloedge(tlist,halohead,&eedge); 
  900.  
  901.     } else if(head->type == EDGETYPE_INT) {
  902. /* if internal edge */
  903.         curwidth =  FLERP(faceminwidth,facemaxwidth,head->delc);
  904.         extendedge(head,&eedge,extendface);
  905.         hidehaloedge(tlist,halohead,&eedge);
  906.     } else if(head->type == EDGETYPE_POINT) {
  907. /* if point */
  908.         dohidepoint(tlist,&eedge);
  909.     }
  910.     head = head->next;
  911.     }
  912.     freeedgelist(edgelist);
  913.     freeedgelist(halohead);
  914.     freetilelist(tlist);
  915. }
  916.  
  917. static int bbox2d(e,t)
  918. edge *e;
  919. tile *t;
  920. {
  921.     if(e->xmax<=t->xmin)
  922.     return 0;
  923.     if(t->xmax<=e->xmin)
  924.     return 0;
  925.     if(e->ymax<=t->ymin)
  926.     return 0;
  927.     if(t->ymax<=e->ymin)
  928.     return 0;
  929.     return 1;
  930. }
  931.  
  932. static int bbox3d(e,t)
  933. edge *e;
  934. tile *t;
  935. {
  936.     if(e->xmax<=t->xmin)
  937.     return 0;
  938.     if(t->xmax<=e->xmin)
  939.     return 0;
  940.     if(e->ymax<=t->ymin)
  941.     return 0;
  942.     if(t->ymax<=e->ymin)
  943.     return 0;
  944.     if(e->zmax<=t->zmin)
  945.     return 0;
  946.     if(t->zmax<=e->zmin)
  947.     return 0;
  948.     return 1;
  949. }
  950.  
  951. static int vsame(v1,v2)
  952. VECT *v1, *v2;
  953. {
  954.     if(v1->x != v2->x)
  955.      return 0;
  956.     if(v1->y != v2->y)
  957.      return 0;
  958.     if(v1->z != v2->z)
  959.      return 0;
  960.     return 1;
  961. }
  962.  
  963. static int edgeontri(e,t)
  964. edge *e;
  965. tile *t;
  966. {
  967.     int i, j;
  968.  
  969.     for(i=0; i<3; i++) {
  970.     if(vsame(e->pos+0,t->pos+i)) {
  971.         for(j=0; j<3; j++) {
  972.         if(vsame(e->pos+1,t->pos+j)) {
  973.             fprintf(stderr,"NEVER\n");
  974.             return 1;
  975.         }
  976.         }
  977.         return 0;
  978.     }
  979.     }
  980.     return 0;
  981. }
  982.  
  983. static int edgeintertri(e,t)
  984. edge *e;
  985. tile *t;
  986. {
  987.     int i, in;
  988.     FLOAT dmin, dmax;
  989.     FLOAT d, d0, d1;
  990.  
  991. /* see if the triangle is entirely on one side of the edge */
  992.     dmin = dmax = edgedist2d(&e->edgeeq,t->pos+0);
  993.     for(i=1; i<3; i++) {
  994.     d = edgedist2d(&e->edgeeq,t->pos+i);
  995.     if(dmin>d)
  996.         dmin = d;
  997.     if(dmax<d)
  998.         dmax = d;
  999.     }
  1000.     if(dmin>-TOLERANCE || dmax<TOLERANCE)
  1001.     return INTER_NONE;
  1002.  
  1003. /* see if the edge is outside all triangle edges */
  1004.     in = 0;
  1005.     for(i=0; i<3; i++) {
  1006.     d0 = dmin = dmax = edgedist2d(t->edgeeq+i,e->pos+0);
  1007.     d1 = edgedist2d(t->edgeeq+i,e->pos+1);
  1008.     if(dmin>d1)
  1009.         dmin = d1;
  1010.     if(dmax<d1)
  1011.         dmax = d1;
  1012.     if(dmin>-TOLERANCE)
  1013.         return INTER_NONE;
  1014.     if(dmax<TOLERANCE)
  1015.         in++;
  1016.     }
  1017.     if(in == 3) 
  1018.     return INTER_COVERS;
  1019.     else 
  1020.     return INTER_TOUCHES;
  1021. }
  1022.  
  1023. static int posinside(p,t)
  1024. VECT *p;
  1025. tile *t;
  1026. {
  1027.     int i;
  1028.     FLOAT d;
  1029.  
  1030.     for(i=0; i<3; i++) {
  1031.     d = edgedist2d(t->edgeeq+i,p);
  1032.     if(d>-TOLERANCE)
  1033.         return 0;
  1034.     }
  1035.     return 1;
  1036. }
  1037.  
  1038. static int tritriinter(t1,t2,e)
  1039. tile *t1, *t2;
  1040. edge *e;
  1041. {
  1042.     FLOAT d[3];
  1043.     int i, l, g, il, ig, al, ag;
  1044.     int lpos[3], gpos[3];
  1045.     int ngood, ngot;
  1046.     FLOAT goodparam[6], dot;
  1047.     VECT *goodpos1[6], *goodpos2[6];
  1048.     tile *goodtri[6];
  1049.     VECT pos;
  1050.  
  1051.     if(!bbox3d(t1,t2))
  1052.     return 0;
  1053.     dot = VDOT(&t1->plane,&t2->plane);
  1054.     if(dot<0.0)
  1055.     dot = -dot;
  1056.     if(dot>ALMOSTPLANAR) 
  1057.          return 0;
  1058.     ngood = 0;
  1059.  
  1060.     l = g = 0;
  1061.     for(i=0; i<3; i++) {
  1062.     d[i] = planedist3d(&t1->plane,&t2->pos[i]);
  1063.     if(d[i]<-TOLERANCE) 
  1064.         lpos[l++] = i;
  1065.     else if(d[i]>TOLERANCE)
  1066.         gpos[g++] = i;
  1067.     }
  1068.     if((l==0) || (g==0))
  1069.      return 0;
  1070.     for(il=0; il<l; il++) {
  1071.     for(ig=0; ig<g; ig++) {
  1072.         al = lpos[il];
  1073.         ag = gpos[ig];
  1074.         goodparam[ngood] = d[al]/(d[al]-d[ag]);
  1075.         goodpos1[ngood] = &t2->pos[al];
  1076.         goodpos2[ngood] = &t2->pos[ag];
  1077.         goodtri[ngood] = t1;
  1078.         ngood++;
  1079.     }
  1080.     }
  1081.  
  1082.     l = g = 0;
  1083.     for(i=0; i<3; i++) {
  1084.     d[i] = planedist3d(&t2->plane,&t1->pos[i]);
  1085.     if(d[i]<-TOLERANCE) 
  1086.         lpos[l++] = i;
  1087.     else if(d[i]>TOLERANCE)
  1088.         gpos[g++] = i;
  1089.     }
  1090.     if((l==0) || (g==0))
  1091.      return 0;
  1092.     for(il=0; il<l; il++) {
  1093.     for(ig=0; ig<g; ig++) {
  1094.         al = lpos[il];
  1095.         ag = gpos[ig];
  1096.         goodparam[ngood] = d[al]/(d[al]-d[ag]);
  1097.         goodpos1[ngood] = &t1->pos[al];
  1098.         goodpos2[ngood] = &t1->pos[ag];
  1099.         goodtri[ngood] = t2;
  1100.         ngood++;
  1101.     }
  1102.     }
  1103.     ngot = 0;
  1104.     for(g=0; g<ngood; g++) {
  1105.     VLERP(goodpos1[g],goodpos2[g],&pos,goodparam[g]);
  1106.     if(posinside(&pos,goodtri[g])) {    
  1107.         e->pos[ngot] = pos; 
  1108.         ngot++;
  1109.         if(ngot == 2) {
  1110.         edgedomain(e);
  1111.         return 1;
  1112.         } 
  1113.     }
  1114.     }
  1115.     return 0;
  1116. }
  1117.  
  1118. static int couldhide(e,t)
  1119. edge *e;
  1120. tile *t;
  1121. {
  1122.     if(t->zmax<=e->zmin)
  1123.      return 0;
  1124.     else
  1125.      return 1;
  1126. }
  1127.  
  1128. static int edgeinbackoftriplane(e,t,d0,d1)
  1129. edge *e;
  1130. tile *t;
  1131. FLOAT *d0, *d1;
  1132. {
  1133.     *d0 = planedist3d(&t->plane,e->pos+0);
  1134.     *d1 = planedist3d(&t->plane,e->pos+1);
  1135.     if( ((*d0)<-TOLERANCE) || ((*d1)<-TOLERANCE) )
  1136.     return 1;
  1137.     else
  1138.     return 0;
  1139. }
  1140.  
  1141. static int trisplitedge(e,t,e1,e2)
  1142. edge *e;
  1143. tile *t;
  1144. edge *e1, *e2;
  1145. {
  1146.     int i;
  1147.     FLOAT d0, d1, dmin, dmax;
  1148.     FLOAT param;
  1149.  
  1150.     for(i=0; i<3; i++) {
  1151.     d0 = dmin = dmax = edgedist2d(t->edgeeq+i,e->pos+0);
  1152.     d1 = edgedist2d(t->edgeeq+i,e->pos+1);
  1153.     if(dmin>d1)
  1154.         dmin = d1;
  1155.     if(dmax<d1)
  1156.         dmax = d1;
  1157.     if(dmax>TOLERANCE && dmin<-TOLERANCE) {
  1158.         param = -d0/(d1-d0);
  1159.         d0 = dmin = dmax = edgedist2d(&e->edgeeq,t->pos+i);
  1160.         d1 = edgedist2d(&e->edgeeq,t->pos+((i+1)%3));
  1161.         if(dmin>d1)
  1162.         dmin = d1;
  1163.         if(dmax<d1)
  1164.         dmax = d1;
  1165.         if(dmax>-TOLERANCE && dmin<TOLERANCE) {
  1166.             e1->pos[0] = e->pos[0]; 
  1167.             VLERP(e->pos+0,e->pos+1,e1->pos+1,param);
  1168.         edgedomain(e1);
  1169.         e1->edgeeq = e->edgeeq;
  1170.  
  1171.             VLERP(e->pos+0,e->pos+1,e2->pos+0,param);
  1172.             e2->pos[1] = e->pos[1]; 
  1173.         edgedomain(e2);
  1174.         e2->edgeeq = e->edgeeq;
  1175.  
  1176.         return 1;
  1177.         }
  1178.     }
  1179.     }
  1180.     return 0;
  1181. }
  1182.  
  1183. static void planesplitedge(e,p,e1,e2)
  1184. edge *e;
  1185. VECT *p;
  1186. edge *e1, *e2;
  1187. {
  1188.     e1->pos[0] = e->pos[0]; 
  1189.     e1->pos[1] = *p;
  1190.     edgedomain(e1);
  1191.     e1->edgeeq = e->edgeeq;
  1192.     e2->pos[0] = *p;
  1193.     e2->pos[1] = e->pos[1];
  1194.     edgedomain(e2);
  1195.     e2->edgeeq = e->edgeeq;
  1196. }
  1197.  
  1198. static void hidehaloedge(tlist,halo,e)
  1199. tile *tlist;
  1200. edge *halo;
  1201. edge *e;
  1202. {
  1203.     handdown();
  1204.     dohidehaloedge(tlist,halo,e,0);
  1205. }
  1206.  
  1207.  
  1208. static int haloedge(e,halo,e1,e2)
  1209. edge *e, *halo;
  1210. edge *e1, *e2;
  1211. {
  1212.     FLOAT d0, d1, del;
  1213.     FLOAT param, ze, zh;
  1214.     FLOAT p1, p2;
  1215.     int ret;
  1216.  
  1217. /* classify halo end points wrt edge */
  1218.     d0 = edgedist2d(&e->edgeeq,halo->pos+0);
  1219.     d1 = edgedist2d(&e->edgeeq,halo->pos+1);
  1220.     if(d1>d0) {
  1221.     if(d1<TOLERANCE || d0>-TOLERANCE)
  1222.         return -1;
  1223.     } else {
  1224.     if(d0<TOLERANCE || d1>-TOLERANCE)
  1225.         return -1;
  1226.     }
  1227.     param = -d0/(d1-d0);
  1228.     zh = FLERP(halo->pos[0].z,halo->pos[1].z,param);
  1229.  
  1230. /* classify edge end points wrt halo */
  1231.     d0 = edgedist2d(&halo->edgeeq,e->pos+0);
  1232.     d1 = edgedist2d(&halo->edgeeq,e->pos+1);
  1233.     if(d1>d0) {
  1234.     if(d1<TOLERANCE || d0>-TOLERANCE)
  1235.         return -1;
  1236.     del = d1-d0;
  1237.     } else {
  1238.     if(d0<TOLERANCE || d1>-TOLERANCE)
  1239.         return -1;
  1240.     del = d0-d1;
  1241.     }
  1242.     param = -d0/(d1-d0);
  1243.     ze = FLERP(e->pos[0].z,e->pos[1].z,param);
  1244.  
  1245. /* compare the depths, if halo in back of edge, return */
  1246.     if(zh<(ze+TOLERANCE))
  1247.     return -1;
  1248.  
  1249. /* find parameter value for split edge */
  1250.     p1 = param-(halowidth/del);
  1251.     p2 = param+(halowidth/del);
  1252.     ret = 0;
  1253.     if(p1>0.0) {
  1254.     e1->pos[0] = e->pos[0]; 
  1255.     VLERP(e->pos+0,e->pos+1,e1->pos+1,p1);
  1256.     edgedomain(e1);
  1257.     e1->edgeeq = e->edgeeq;
  1258.     ret |= 1;
  1259.     }
  1260.     if(p2<1.0) {
  1261.     e2->pos[1] = e->pos[1]; 
  1262.     VLERP(e->pos+0,e->pos+1,e2->pos+0,p2);
  1263.     edgedomain(e2);
  1264.     e2->edgeeq = e->edgeeq;
  1265.     ret |= 2;
  1266.     }
  1267.     return ret;
  1268. }
  1269.  
  1270. static void dohidehaloedge(tlist,halo,e,level)
  1271. tile *tlist;
  1272. edge *halo;
  1273. edge *e;
  1274. int level;
  1275. {
  1276.     int stat, n;
  1277.     FLOAT top;
  1278.     edge e1, e2;
  1279.  
  1280.     top = e->ymax;
  1281.     while(halo) {
  1282.     if(halo->ymin>top)
  1283.         break;
  1284.     if( bbox2d(e,halo) && couldhide(e,halo)) {
  1285.         n=haloedge(e,halo,&e1,&e2);
  1286.         switch(n) {
  1287.         case 0:
  1288.             return;
  1289.         case 1:
  1290.             dohidehaloedge(tlist,halo,&e1,level+1);
  1291.             return;
  1292.         case 2:
  1293.             dohidehaloedge(tlist,halo,&e2,level+1);
  1294.             return;
  1295.         case 3:
  1296.             dohidehaloedge(tlist,halo,&e1,level+1);
  1297.             dohidehaloedge(tlist,halo,&e2,level+1);
  1298.             return;
  1299.         }
  1300.     }
  1301.     halo = halo->next;
  1302.     }
  1303.  
  1304. /* if not halo'ed at all, put out the line */
  1305.     dohideedge(tlist,e,0);
  1306. }
  1307.  
  1308. static void dohideedge(tlist,e,level)
  1309. tile *tlist;
  1310. edge *e;
  1311. int level;
  1312. {
  1313.     int stat;
  1314.     edge e1, e2;
  1315.     FLOAT top, d0, d1, param;
  1316.     VECT planepos;
  1317.  
  1318.     top = e->ymax;
  1319.     while(tlist) {
  1320.     if(tlist->ymin>top)
  1321.         break;
  1322.     if( (tlist->transparent==0) && bbox2d(e,tlist) && 
  1323.         couldhide(e,tlist) && edgeinbackoftriplane(e,tlist,&d0,&d1)) {
  1324.  
  1325. /* edge crosses plane of triangle */
  1326.         if((d0*d1)<-TOLERANCE) {    
  1327.         param = d0/(d0-d1);
  1328.         VLERP(e->pos+0,e->pos+1,&planepos,param);
  1329.         if(posinside(&planepos,tlist)) {    /* edge goes thru */
  1330.             planesplitedge(e,&planepos,&e1,&e2);
  1331.             dohideedge(tlist,&e1,level+1);
  1332.             dohideedge(tlist,&e2,level+1);
  1333.             return;
  1334.         }
  1335.         }
  1336.  
  1337. /* 2d triangle intersect */
  1338.         stat = edgeintertri(e,tlist);
  1339.         if(stat == INTER_TOUCHES) {
  1340.         if(trisplitedge(e,tlist,&e1,&e2)) {
  1341.             dohideedge(tlist,&e1,level+1);
  1342.             dohideedge(tlist,&e2,level+1);
  1343.             return;
  1344.         } else {
  1345.             fprintf(stderr,"split failed\n");
  1346.             exit(1);
  1347.         }
  1348.         }
  1349.         if(stat == INTER_COVERS) 
  1350.         return;
  1351.     }
  1352.     tlist = tlist->next;
  1353.     }
  1354.  
  1355. /* if not obscured at all, put out the line */
  1356.     putline(e->pos+0,e->pos+1,curwidth);
  1357. }
  1358.  
  1359. static void dohidepoint(tlist,e)
  1360. tile *tlist;
  1361. edge *e;
  1362. {
  1363.     int stat;
  1364.     edge e1, e2;
  1365.     FLOAT top, d0, d1, param;
  1366.     VECT planepos;
  1367.  
  1368.     top = e->ymax;
  1369.     while(tlist) {
  1370.     if(tlist->ymin>top)
  1371.         break;
  1372.     if( bbox2d(e,tlist) && couldhide(e,tlist)) {
  1373.         if(!posinside(&e->pos[0],tlist)) {    /* XXXX what */
  1374.         return;
  1375.         }
  1376.      }
  1377.     tlist = tlist->next;
  1378.     }
  1379.  
  1380. /* if not obscured at all, put out the line */
  1381.     putpoint((float *)e->pos+0,curwidth);
  1382. }
  1383.  
  1384. static void putpoint(float *p, float width)
  1385. {
  1386.     if(width!=putwidth) {
  1387.          putwidth = width;
  1388.     widthfunc(putwidth);
  1389.     }
  1390.     linefunc(p,p);
  1391. }
  1392.  
  1393. static int compar(p0,p1)
  1394. tile **p0, **p1;
  1395. {
  1396.     FLOAT y0, y1;
  1397.  
  1398.     y0 = (*p0)->ymin;
  1399.     y1 = (*p1)->ymin;
  1400.     if(y0<y1)
  1401.     return 1;
  1402.     if(y0==y1)
  1403.     return 0;
  1404.     else
  1405.     return -1;
  1406. }
  1407.  
  1408. static tile *ysortlist(tiles)
  1409. tile *tiles;
  1410. {
  1411.     tile *t, **all, **tpp;
  1412.     int i, n;
  1413.  
  1414.     n = 0; 
  1415.     t = tiles;
  1416.     while(t) {
  1417.     t = t->next;
  1418.     n++;
  1419.     }
  1420.     all = (tile **)mymalloc(n*sizeof(tile*));
  1421.     t = tiles;
  1422.     tpp = all;
  1423.     while(t) {
  1424.     *tpp++ = t;
  1425.     t = t->next;
  1426.     }
  1427.     qsort(all,n,sizeof(tile *),compar);
  1428.     t = 0;
  1429.     tpp = all;
  1430.     while(n--) {
  1431.     (*tpp)->next = t;
  1432.     t = *tpp++;
  1433.     }
  1434.     free(all);
  1435.     return t;
  1436. }
  1437.  
  1438. static void putline(p0,p1,width)
  1439. VECT *p0, *p1;
  1440. FLOAT width;
  1441. {
  1442.     float v0[3], v1[3];
  1443.  
  1444.     v0[0] = p0->x;
  1445.     v0[1] = p0->y;
  1446.     v0[2] = 0.0;
  1447.     v1[0] = p1->x;
  1448.     v1[1] = p1->y;
  1449.     v1[2] = 0.0;
  1450.     if(width!=putwidth) {
  1451.          putwidth = width;
  1452.     widthfunc(putwidth);
  1453.     }
  1454.     handline(linefunc,v0,v1);
  1455. }
  1456.  
  1457. #ifdef DASHEDLINES
  1458. dashedge(e)
  1459. edge *e;
  1460. {
  1461.     setlinestyle(1);
  1462.     bgnline();
  1463.     V2F(&e->pos[0]);
  1464.     V2F(&e->pos[1]);
  1465.     endline();
  1466.     setlinestyle(0);
  1467. }
  1468. #endif
  1469.  
  1470. /*
  1471.  *
  1472.  *    graphical debugging stuff
  1473.  *
  1474.  */
  1475. #ifdef NOTDEF
  1476.  
  1477. #define POSDEL 0.01
  1478.  
  1479. drawtilelist(tlist)
  1480. tile *tlist;
  1481. {
  1482.     reshapeviewport();
  1483.     ortho(-1.1*ASPECT,1.1*ASPECT,-1.1,1.1,-2.0,2.0);
  1484.     rgb(1.0,1.0,1.0);
  1485.     clear();
  1486.     while(tlist) {
  1487.     cpack(0x000000ff);
  1488.     drawtile(tlist);
  1489.     tlist = tlist->next;
  1490.     }
  1491. }
  1492.  
  1493. drawpos(p)
  1494. VECT *p;
  1495. {
  1496.     move2(p->x-POSDEL,p->y);
  1497.     draw2(p->x+POSDEL,p->y);
  1498.     move2(p->x,p->y-POSDEL);
  1499.     draw2(p->x,p->y+POSDEL);
  1500. }
  1501.  
  1502. tridraw(tri)
  1503. trilisttri *tri;
  1504. {
  1505.     cpack(0x000000ff);
  1506.     bgnclosedline();
  1507.     V2F(&tri->x0);
  1508.     V2F(&tri->x1);
  1509.     V2F(&tri->x2);
  1510.     endclosedline();
  1511. }
  1512.  
  1513. drawinter(e,t)
  1514. edge *e;
  1515. tile *t;
  1516. {
  1517.     FLOAT xmin, xmax;
  1518.     FLOAT ymin, ymax;
  1519.     FLOAT xavg, yavg;
  1520.  
  1521.     xmin = MIN(e->xmin,t->xmin);
  1522.     xmax = MAX(e->xmax,t->xmax);
  1523.     ymin = MIN(e->ymin,t->ymin);
  1524.     ymax = MAX(e->ymax,t->ymax);
  1525.     xavg = (xmin+xmax)/2.0;
  1526.     yavg = (ymin+ymax)/2.0;
  1527.     pushmatrix();
  1528.     scale(10.0,10.0,1.0);
  1529.     translate(-xavg,-yavg,0.0);
  1530.     translate(-0.05,-0.05,0.0);
  1531.     drawedge(e);
  1532.     drawtile(t);
  1533.     popmatrix();
  1534. }
  1535.  
  1536. drawedge(e)
  1537. edge *e;
  1538. {
  1539.     bgnline();
  1540.     V2F(e->pos+0);
  1541.     V2F(e->pos+1);
  1542.     endline();
  1543. }
  1544.  
  1545. drawtile(t)
  1546. tile *t;
  1547. {
  1548.     bgnclosedline();
  1549.     V2F(t->pos+0);
  1550.     V2F(t->pos+1);
  1551.     V2F(t->pos+2);
  1552.     endclosedline();
  1553. }
  1554.  
  1555. printtile(t)
  1556. tile *t;
  1557. {
  1558.     int i;
  1559.  
  1560.     for(i=0; i<3; i++) {
  1561.     fprintf(stderr,"t%d: %f %f %f\n",
  1562.                 i,t->pos[i].x,t->pos[i].y,t->pos[i].z);
  1563.     }
  1564.     fprintf(stderr,"\n");
  1565. }
  1566.  
  1567. printedge(e)
  1568. edge *e;
  1569. {
  1570.     fprintf(stderr,"p0: %f %f %f c0: 0x%08x\n",
  1571.             e->pos[0].x,e->pos[0].y,e->pos[0].z,e->col[0]);
  1572.     fprintf(stderr,"p1: %f %f %f c1: 0x%08x\n",
  1573.             e->pos[1].x,e->pos[1].y,e->pos[1].z,e->col[1]);
  1574.     fprintf(stderr,"\n");
  1575. }
  1576.  
  1577. #endif
  1578.